import java.util.ArrayList;
import java.util.List;

public class Offer28 {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        if (root.left==null&&root.right==null){
            return true;
        }
        if (root.left!=null&&root.right==null||root.right!=null&&root.left==null) return false;
        boolean result = true;
        TreeNode left = root.left;
        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        TreeNode right = root.right;
        dfsleft(left,leftList);
        dfsright(right,rightList);
        System.out.println(leftList);
        System.out.println(rightList);
        if (leftList.size()!=rightList.size()) return false;
        for (int i = 0; i < leftList.size(); i++) {
            if (leftList.get(i)!=rightList.get(i)) return false;
        }
        return result;
    }
    public void dfsleft(TreeNode leftRoot,List<Integer> leftList){
        if (leftRoot==null){
            leftList.add(null);
            return;
        }
        leftList.add(leftRoot.val);
        dfsleft(leftRoot.left,leftList);
        dfsleft(leftRoot.right,leftList);
    }
    public void dfsright(TreeNode rightRoot,List<Integer> rightList){
        if (rightRoot==null){
            rightList.add(null);
            return;
        }
        rightList.add(rightRoot.val);
        dfsright(rightRoot.right,rightList);
        dfsright(rightRoot.left,rightList);
    }

}
